/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lenovo
 * Date: 2023 -04 -09
 * Time: 14:26
 */
public class MyList {
    static class LinkList {
        public int data;
        public LinkList next;

        public LinkList(int data) {
            this.data = data;
        }
        public LinkList(){

        }
    }

    public LinkList head;

    /* public void initList(){
         LinkList n1=new LinkList(12);
         LinkList n2=new LinkList(23);
         LinkList n3=new LinkList(34);
         LinkList n4=new LinkList(45);
         n1.next=n2;
         n2.next=n3;
         n3.next=n4;
         head=n1;
     }*/
    //打印单链表
    public void display() {
        LinkList cur = head;
        if (head == null) {
            System.out.println("NULL");
        }
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display(LinkList str) {
        LinkList cur = str;
        if (str == null) {
            System.out.println("NULL");
        }
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //头插法
    public void addFirst(int data) {
        LinkList cur = head;
        LinkList newNode = new LinkList(data);
        newNode.next = head;
        head = newNode;
    }

    //尾插法
    public void addLast(int data) {
        if (head == null) {
            LinkList newNode = new LinkList(data);
            head = newNode;
            return;
        }
        LinkList cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        LinkList newNode = new LinkList(data);
        cur.next = newNode;
        cur = newNode;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index, int data) {
        if (index < 0 || index > size()) {//012345
            return false;
        }
        if (index == 0) {
            addFirst(data);
            return true;
        }
        if (index == size()) {
            addLast(data);
            return true;
        }
        int count = 0;
        LinkList cur = head;
        while (cur != null) {
            count++;
            if (count == index) {
                break;
            }
            cur = cur.next;
        }
        LinkList newNode = new LinkList(data);
        newNode.next = cur.next;
        cur.next = newNode;
        return true;
    }

    //得到单链表的长度
    public int size() {
        int count = 0;
        LinkList cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        LinkList cur = head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (contains(key) == false) {
            System.out.println("没有该节点");
        } else {
            if (head.data == key) {
                head = head.next;
            } else {
                LinkList cur = head;
                LinkList pre = head.next;
                while (pre != null) {
                    if (pre.data == key) {
                        cur.next = pre.next;
                        return;
                    }
                    pre = pre.next;
                    cur = cur.next;
                }
            }
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        LinkList cur = head;
        LinkList pre = head.next;
        while (pre != null) {
            if (pre.data == key) {
                cur.next = pre.next;
                pre = pre.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        if (head.data == key) {
            head = head.next;
        }
    }


    public void clear() {
        head = null;
    }





//找中间节点
    public LinkList acquireIntermidNode(){
        LinkList slow=head;
        LinkList fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    //反转链表
    public LinkList reverseList(){
        LinkList cur=head;
        LinkList curNext=cur.next;
        cur=cur.next;
        head.next=null;
        while(cur!=null){
            curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
    public LinkList reverseList(LinkList mid){
        LinkList cur=mid;
        LinkList curNext=cur.next;
        cur=cur.next;
        mid.next=null;
        while(cur!=null){
            curNext=cur.next;
            cur.next=mid;
            mid=cur;
            cur=curNext;
        }
        return mid;
    }
    //判断回文
    public boolean palindrome(){
        LinkList mid=acquireIntermidNode();
        LinkList last=reverseList(mid);
        LinkList first=head;
        int flag=0;
       while(first.data==last.data){
           first=first.next;
           last=last.next;
           if(first==last&&first==null){
               flag=1;
               break;
           }
        }
       if(flag==1){
           return true;
       }else{
           return false;
       }
    }
    //获得倒数第K个结点（快慢指针法）
   public LinkList findLast_K(int index){
        LinkList fast=head;
        LinkList slow =head;
        if(index<0||index>size()||head==null){
            return null;
        }
        while((index-1)!=0){
            fast=fast.next;
            index--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
   }
   //让值小于x的到链表左边，值大x的到链表右边，原顺序保持不变
    public  LinkList partition(LinkList head,int x) {
        LinkList bs = null;
        LinkList be = null;
        LinkList as = null;
        LinkList ae = null;
        LinkList cur = head;
        while (cur != null) {
            if (cur.data < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be=cur;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae=cur;
                }
            }
            cur = cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null) {
            ae.next = null;
        }
        return bs;
    }
}
